程序代写代做 graph C finance database AI Chapter 2: 
 Introduction to the Relational Model

Chapter 2: 
 Introduction to the Relational Model
Database System Concepts, 6th Ed.
©Silberschatz, Korth and Sudarshan

See www.db-book.com for conditions on re-use

Example of a Relation
attributes (or columns)
tuples (or rows)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.2 ©Silberschatz, Korth and Sudarshan

Attribute Types
■ The set of allowed values for each attribute is called the domain of the attribute
■ Attribute values are (normally) required to be atomic; that is, indivisible
■ The special value null is a member of every domain
■ The null value causes complications in the definition of many
operations
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.3 ©Silberschatz, Korth and Sudarshan

Relation Schema and Instance
■ A1, A2, …, An are attributes
■ R = (A1, A2, …, An ) is a relation schema Example:
instructor = (ID, name, dept_name, salary)
■ Formally, given sets D1, D2, …. Dn a relation r is a subset of 
 D1 x D2 x … x Dn

Thus, a relation is a set of n-tuples (a1, a2, …, an) where each ai
■ The current values (relation instance) of a relation are specified by
a table
■ An element t of r is a tuple, represented by a row in a table
∈ Di
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.4 ©Silberschatz, Korth and Sudarshan

Relations are Unordered
■ Order of tuples is irrelevant (tuples may be stored in an arbitrary order) ■ Example: instructor relation with unordered tuples
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.5 ©Silberschatz, Korth and Sudarshan

Database
■ A database consists of multiple relations
■ Information about an enterprise is broken up into parts
instructor 
 student 
 advisor
■ Bad design: 

univ (instructor_ID, name, dept_name, salary, student_ID, ..)

results in
● repetitionofinformation(e.g.,twostudentshavethesameinstructor) ● the need for null values (e.g., represent an student with no advisor)
■ Normalization theory (Chapter 7) deals with how to design “good” relational schemas
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.6 ©Silberschatz, Korth and Sudarshan

Keys
■ LetK⊆R
■ K is a superkey of R if values for K are sufficient to identify a unique
tuple of any possible relation r(R)
● Example: {ID} and {ID, name} are both superkeys of instructor. ● However:{name}isnotasuperkey.(Why?)
■ Superkey K is a candidate key if K is minimal
 Example: {ID} is a candidate key for Instructor
■ One of the candidate keys is selected to be the primary key.
● whichone?
■ Foreign key constraint: Value in one relation must appear in another
● Referencingrelation ● Referencedrelation
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.7 ©Silberschatz, Korth and Sudarshan

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.8 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.9 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Keys and Foreign Keys: Example
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.10 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Schema Diagram for University Database
student
ID
name dept_name tot_cred
section
course
course_id
title dept_name credits
department
dept_name
building budget
advisor
s_id
i_id
course_id sec_id semester year building room_no time_slot_id
instructor
ID
name dept_name salary
prereq
course_id
prereq_id
classroom
building
room_no capacity
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.11 ©Silberschatz, Korth and Sudarshan
ID
course_id sec_id semester year
takes
ID
course_id sec_id semester year grade
time_slot
time_slot_id
day start_time end_time
teaches

Relational Query Languages
■ Procedural vs.non-procedural, or declarative ■ “Pure” languages:
● Relational algebra (procedural)
● Relational calculus (non-procedural)
! Domain relational calculus (DRC)
! Tuple relational calculus (TRC) ■ Non-pure, real languages:
● SQL
● Query By Example (QBE)
■ But first we introduce relational operators
● Selection, projection, cross product, …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.12 ©Silberschatz, Korth and Sudarshan

■ Relation r
Selection of tuples
■ Select tuples with A=B and D>5
l σA=BandD>5 (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.13 ©Silberschatz, Korth and Sudarshan

Selection of Columns (Attributes)
■ Relation r:
■ Select A and C l Projection
l Π A, C (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.14 ©Silberschatz, Korth and Sudarshan

Joining two relations – Cartesian Product
■ Relations r, s:
rxs
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.15 ©Silberschatz, Korth and Sudarshan

Union of two relations
■ Relations r, s:
■ r∪s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.16 ©Silberschatz, Korth and Sudarshan

■ Relations r, s:
Set difference of two relations
■ r–s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.17 ©Silberschatz, Korth and Sudarshan

Set Intersection of two relations
■ Relation r, s:
■ r∩s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.18 ©Silberschatz, Korth and Sudarshan

Joining two relations – Natural Join
■ Let r and s be relations on schemas R and S respectively. 

Then, the “natural join” of relations R and S is a relation on schema R ∪ S obtained as follows:
● Consider each pair of tuples tr from r and ts from s.
● If tr and ts have the same value on each of the attributes in R ∩ S, add a tuple t to the result, where
! t has the same value as tr on r ! t has the same value as ts on s
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.19 ©Silberschatz, Korth and Sudarshan

■ Relations r, s:
■ Natural Join l r s
Natural Join Example
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.20 ©Silberschatz, Korth and Sudarshan

Overview of Operators
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.21 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Suppose you want to design a database for a bakery selling cakes
■ The bakery makes certain cakes: Apple Pie, Chocolate Cake, etc ■ Cakes have a price and also need certain ingredients
■ Customer can order cakes, and then pick them up on some date
■ Bakery also wants to keep track of how much ingredients they have ■ Customers may want to search by ingredient
(e.g., “cakes with chocolate but without peanuts”) ■ Let’s design a relational schema for this problem …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.22 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Let’s design a relational schema for this problem …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.23 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.24 ©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
■ Foreign keys:
cid cname cname iname
CUSTOMER
ORDER
CAKE
USED_IN
INGREDIENT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.25
©Silberschatz, Korth and Sudarshan

Database Design Example
■ Possible schema:
CUSTOMER (cid, name, phone, ccn)

CAKE (cname, price, slices)

ORDER (oid, cid, cname, pickupdate, orderdate, oprice) INGREDIENT (iname, price, amountleft)
USED_IN (cname, iname, amount)
■ Possible queries:
● IDs of customers with name “J. Smith”
● Names of cakes containing more than 12oz of chocolate
● Names of customers who bought “apple pie”
● IDs of customers who have never bought a cake with peanuts
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.26 ©Silberschatz, Korth and Sudarshan

Chapter 6: Formal Relational Query Languages
Relational Algebra Domain Relational Calculus (Tuple Relational Calculus) Query By Example
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.27 ©Silberschatz, Korth and Sudarshan

Relational Algebra
■ Procedural language
■ Based on relational operations introduced in chapter 2 ■ Three sets of RA operations
● Basic RA operations:
! select, project, union, set diff., cartesian product, rename
● Additional RA operations:
! Can be expressed using basic ones
! But make it easier to write queries ! intersection, assignment, joins, division
● Extended RA:
! Increases power of RA
! Cannot be expressed with basic RA ! Aggregation and group_by
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.28 ©Silberschatz, Korth and Sudarshan

Relational Algebra
■ Six basic operators
● select: σ
● project: ∏
● union: ∪
● set difference: –
● Cartesian product: x
● rename: ρ
■ Alloperatorstakeoneortworelationsasinputsandproduceanew
relation as a result
■ Additionaloperatorsdefinedontopofthese6later
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.29 ©Silberschatz, Korth and Sudarshan

■ Relation r
Select Operation – Example
¡ σA=B ^ D > 5 (r)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.30 ©Silberschatz, Korth and Sudarshan

Select Operation ■ p is called the selection predicate


σp(r) = {t | t ∈ r and p(t)}

Where p is a formula in propositional calculus consisting of terms connected by : ∧ (and), ∨ (or), ¬ (not)

Each term is one of:
op or whereopisoneof: =,≠,>,≥.<.≤
 Example of selection:
 σ dept_name=“Physics”(instructor) ■ Notation: σp(r) ■ Defined as:
 ■ 
 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.31 ©Silberschatz, Korth and Sudarshan ■ Relation r: Project Operation – Example ■ ∏A,C (r) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.32 ©Silberschatz, Korth and Sudarshan Project Operation ∏ A ,A ,...,A (r) 12k ■ Notation:
 where A1, A2 are attribute names and r is a relation name. ■ The result is defined as the relation of k columns obtained by erasing the columns that are not listed ■ Duplicate rows removed from result, since relations are sets ■ Example: To eliminate the dept_name attribute of instructor
 
 ∏ID, name, salary (instructor) 
 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.33 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: ■ r∪s: Union Operation – Example Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.34 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: Set difference of two relations ■ r – s: Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.35 ©Silberschatz, Korth and Sudarshan Cartesian-Product Operation – Example ■ Relations r, s: ■ rxs: Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.36 ©Silberschatz, Korth and Sudarshan Cartesian-Product Operation ■ Notation r x s ■ Defined as: r x s = {t q | t ∈ r and q ∈ s}
 ■ Assume that attributes of r(R) and s(S) are disjoint. (That is, R ∩ S = ∅). ■ If attributes of r(R) and s(S) are not disjoint, then renaming must be used. Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.37 ©Silberschatz, Korth and Sudarshan Composition of Operations ■ Can build expressions using multiple operations ■ Example: σA=C(r x s) ■ rxs ■ σA=C(rxs) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.38 ©Silberschatz, Korth and Sudarshan Rename Operation ■ Allowsustoname,andthereforetoreferto,theresultsofrelational- algebra expressions. ■ Allowsustorefertoarelationbymorethanonename. ■ Example: ρx(E)
 returns the expression E under the name X ■ If a relational-algebra expression E has arity n, then ρx(A ,A ,...,A )(E) 12n returns the result of expression E under the name X, and with the attributes renamed to A1 , A2 , ...., An . ■ E.g.. Given relation CAKE(cname, price, slices) ρ cheapcake(cakename, price, slices) ( σ price < 10 (CAKE) ) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.39 ©Silberschatz, Korth and Sudarshan Formal Definition ■ Abasicexpressionintherelationalalgebraconsistsofeitheroneofthe following: ● A relation in the database ● A constant relation ■ Let E1 and E2 be relational-algebra expressions; the following are all relational-algebra expressions: ● E1∪E2 ● E1–E2 ● E1xE2 ● σp (E1), P is a predicate on attributes in E1 ● ∏s(E1), S is a list consisting of some of the attributes in E1 ● ρ x (E1), x is the new name for the result of E1 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.40 ©Silberschatz, Korth and Sudarshan Additional Operations We define additional operations that do not add any power to the relational algebra, but that simplify common queries. ■ Set intersection ■ Natural join ■ Assignment ■ Outer join ■ Division Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.41 ©Silberschatz, Korth and Sudarshan Set-Intersection Operation – Example ■ Relation r, s: ■ r∩s Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.42 ©Silberschatz, Korth and Sudarshan Natural-Join Operation ■ Notation: r s ■ Let r and s be relations on schemas R and S respectively. 
 Then, r s is a relation on schema R ∪ S obtained as follows: ● Considereachpairoftuplestrfromrandtsfroms. ● IftrandtshavethesamevalueoneachoftheattributesinR∩S,add a tuple t to the result, where ! t has the same value as tr on r ! t has the same value as ts on s ■ Example: R = (A, B, C, D) S = (E, B, D) ● Resultschema=(A,B,C,D,E) ● r s is defined as:
 ∏r.A, r.B, r.C, r.D, s.E (σr.B = s.B ∧ r.D = s.D (r x s)) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.43 ©Silberschatz, Korth and Sudarshan ■ Relations r, s: ■ r s Natural Join Example Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.44 ©Silberschatz, Korth and Sudarshan Natural Join and Theta Join ■ Find the names of all instructors in the Comp. Sci. department together with the course titles of all the courses that the instructors teach ● ∏ name, title (σ dept_name=“Comp. Sci.” (instructor teaches course)) ■ Natural join is associative ● (instructor teaches) course is equivalent to
 instructor (teaches course) ■ Natural join is commutative ● instruct teaches is equivalent to
 teaches instructor ■ The theta join operation r θ s is defined as ● r θ s = σθ (r x s) where θ (theta) is an arbitrary condition Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.45 ©Silberschatz, Korth and Sudarshan Natural Join and Theta Join ■ Find the names of all instructors in the Comp. Sci. department together with the course titles of all the courses that the instructors teach ● ∏ name, title (σ dept_name=“Comp. Sci.” (instructor teaches course)) ■ Natural join is associative ● (instructor teaches) course is equivalent to
 instructor (teaches course) ■ Natural join is commutative ● instruct teaches is equivalent to
 teaches instructor ■ The theta join operation r θ s is defined as ● r θ s = σθ (r x s) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.46 ©Silberschatz, Korth and Sudarshan Careful: this assumes instructors only teach in “their” department! Assignment Operation ■ The assignment operation (←) provides a convenient way to express complex queries. ● Write query as a sequential program consisting of ! a series of assignments ! followed by an expression whose value is displayed as a result of the query. ● Assignment must always be made to a temporary relation variable. ● Motivation from algebra: suppose you want to compute y = (a+b+c)^2 + (a+b+c)^3 + (a+b+c)^4 Shorter: x = a+b+c y = x^2 + x^3 + x^4 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.47 ©Silberschatz, Korth and Sudarshan Outer Join ■ Anextensionofthejoinoperationthatavoidslossofinformation. ■ Computes the join and then adds tuples form one relation that does not match tuples in the other relation to the result of the join. ■ Uses null values: ● null signifies that the value is unknown or does not exist ● All comparisons involving null are (roughly speaking) false by definition. ! We shall study precise meaning of comparisons with nulls later Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.48 ©Silberschatz, Korth and Sudarshan ■ Relation instructor1 Outer Join – Example ID name dept_name 10101 12121 15151 Srinivasan Wu Mozart Comp. Sci. Finance Music ■ Relation teaches1 ID course_id 10101 12121 76766 CS-101 FIN-201 BIO-101 Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.49 ©Silberschatz, Korth and Sudarshan ■ Join 
 
 instructor teaches Outer Join – Example ID name dept_name course_id 10101 12121 Srinivasan Wu Comp. Sci. Finance CS-101 FIN-201 ■ Left Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 Srinivasan Wu Mozart Comp. Sci. Finance Music CS-101 FIN-201 null Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.50 ©Silberschatz, Korth and Sudarshan Outer Join – Example ■ Right Outer Join instructor teaches ID name dept_name course_id 10101 12121 76766 Srinivasan Wu null Comp. Sci. Finance null CS-101 FIN-201 BIO-101 ■ Full Outer Join instructor teaches ID name dept_name course_id 10101 12121 15151 76766 Srinivasan Wu Mozart null Comp. Sci. Finance Music null CS-101 FIN-201 null BIO-101 ■ Outer join can be expressed using basic operations ● e.g.r scanbewrittenas (r s) U(r–∏R(r s) x{(null,...,null)}) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.51 ©Silberschatz, Korth and Sudarshan Theta vs. Natural vs. Outer Join ■ CUSTOMER (cid, cname, joindate) PURCHASE (cid, pid, buydate) ■ Theta Join: more general than Natural Join ■ Natural Join: special case, join on common attributes ■ Works 95% of time, but what if we use “date” in both? ■ Inner versus outer join is separate issue Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.52 ©Silberschatz, Korth and Sudarshan Null Values ■ It is possible for tuples to have a null value, denoted by null, for some of their attributes ■ null signifies an unknown value or that a value does not exist. ■ The result of any arithmetic expression involving null is null. ■ Aggregatefunctionssimplyignorenullvalues(asinSQL) ■ For duplicate elimination and grouping, null is treated like any other value, and two nulls are assumed to be the same (as in SQL) Database System Concepts - 6th Edition Modified by T. Suel for CS6083, NYU Tandon, Spring 2020 2.53 ©Silberschatz, Korth and Sudarshan Null Values ■ Comparisons with null values return the special truth value: unknown ● If false was used instead of unknown, then not (A < 5) 
 would not be equivalent to A >= 5 ■ Three-valued logic using the truth value unknown:
● OR:(unknownortrue) =true,
 (unknown or false) = unknown
 (unknown or unknown) = unknown
● AND: (true and unknown) = unknown, (false and unknown) = false,

(unknown and unknown) = unknown
● NOT: (not unknown) = unknown


● InSQL“Pisunknown”evaluatestotrueifpredicatePevaluatesto unknown
■ Result of select predicate is treated as false if it evaluates to unknown
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.54 ©Silberschatz, Korth and Sudarshan

Division Operator
■ Given relations r(R) and s(S), such that S ⊂ R, r ÷ s is the largest relation t(R-S) such that 

txs⊆r
■ E.g. let r(ID, course_id) = ∏ID, course_id (takes ) and

s(course_id) = ∏course_id (σdept_name=“Biology”(course ) 
 then r ÷ s gives us students who have taken all courses offered by
the Biology department
■ Can writer÷sas
temp1 ← ∏R-S (r ) 

temp2 ← ∏R-S ((temp1 x s ) – ∏R-S,S (r ))
 result = temp1 – temp2
● See use of assignment: the result to the right of the ← is assigned to the relation variable on the left of the ←.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.55 ©Silberschatz, Korth and Sudarshan

Division Operation – Example
A
B
■ Relations r, s:
B
α α α β γ δ δ δ ∈ ∈ β
1 2 3 1 1 1 3 4 6 1 2
1 2
s
A
α β
■ r ÷ s:
r
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.56
©Silberschatz, Korth and Sudarshan

■ Relations r, s:
Another Division Example
A
B
C
D
E
D
E
α α α β β γ γ γ
a a a a a a a
a
α γ γ γ γ γ γ β
a a b a b a b
b
1 1 1 1 3 1 1 1
a b
1 1
■ r ÷ s:
r
s
A
B
C
α γ
a a
γ γ
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.57 ©Silberschatz, Korth and Sudarshan

Extended Relational-Algebra-Operations
■ Generalized Projection ■ AggregateFunctions
Generalized Projection
■ Extends the projection operation by allowing arithmetic functions to be used in the projection list.





∏F ,F ,…, F (E) 12n
■ E is any relational-algebra expression
■ Each of F1, F2, …, Fn are are arithmetic expressions involving constants
and attributes in the schema of E.
■ Given relation instructor(ID, name, dept_name, salary) where salary is annual salary, get the same information but with monthly salary
∏ID, name, dept_name, salary/12 (instructor)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.58 ©Silberschatz, Korth and Sudarshan

Aggregate Functions and Operations
■ Aggregation function takes a collection of values and returns a single
value as a result.
avg: average value

min: minimum value
 max: maximum value
 sum: sum of values
 count: number of values
■ Aggregate operation in relational algebra
G ,G ,…,G F (A ),F (A ,…,F (A )(E) 12n1122nn


E is any relational-algebra expression
● G1, G2 …, Gn is a list of attributes on which to group (can be empty) ● Each Fi is an aggregate function
● Each Ai is an attribute name
■ Note: Some books/articles use γ instead of (Calligraphic G) Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.59
©Silberschatz, Korth and Sudarshan

■ Relation r:
Aggregate Operation – Example
A
B
C
α α β β
α β β β
7 7 3 10
■ sum(c) (r)
sum(c )
27
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.60 ©Silberschatz, Korth and Sudarshan

Aggregate Operation – Example
■ Find the average salary in each department dept_name avg(salary) (instructor)
avg_salary
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.61 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name max(salary) as max_sal (instructor)
■ Suppose we want to find instructor who made highest salary ■ Do not nest inside selection operator as follows:
A max(salary) as max_sal (instructor) σsalary = A (instructor)
■ Aisatablewithonerowandonecolumn
■ No nested RA expressions (i.e., tables) inside selection condition
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.62 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name max(salary) as max_sal (instructor)
■ Suppose we want to find instructor who made highest salary ■ Do not nest inside selection operator as follows:
A max(salary) as max_sal (instructor) σsalary = A (instructor) — this is wrong!
■ Aisatablewithonerowandonecolumn
■ No nested RA expressions (i.e., tables) inside selection condition
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.63 ©Silberschatz, Korth and Sudarshan

Aggregate Functions (Cont.)
■ Result of aggregation does not have a name
● Can use rename operation to give it a name
● For convenience, we permit renaming as part of aggregate operation

dept_name avg(salary) as avg_sal (instructor) ■ Correct:
A max(salary) as max_sal (instructor) σsalary = A.max_sal (instructor X A)
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.64 ©Silberschatz, Korth and Sudarshan

Modification of the Database
■ The content of the database may be modified using the following operations:
● Deletion ● Insertion ● Updating
■ All these operations can be expressed using the assignment operator
■ Compute new state of table, then assign it to table
■ But this does not give much insight …
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.65 ©Silberschatz, Korth and Sudarshan

Multiset Relational Algebra
■ Pure relational algebra removes all duplicates ● e.g. after projection
■ Multiset relational algebra retains duplicates, to match SQL semantics
● SQL duplicate retention was initially for efficiency, but is now a feature
■ Multiset relational algebra defined as follows
● selection: has as many duplicates of a tuple as in the input, if the
tuple satisfies the selection
● projection: one tuple per input tuple, even if it is a duplicate
● cross product: If there are m copies of t1 in r, and n copies of t2 in s, therearemxncopiesoft1.t2inr xs
● Other operators similarly defined
! E.g. union: m + n copies, intersection: min(m, n) copies

difference: min(0, m – n) copies
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.66 ©Silberschatz, Korth and Sudarshan

SQL and Relational Algebra
■ select A1, A2, .. An
 from r1, r2, …, rm
 where P
is equivalent to the following expression in multiset relational algebra ∏A1,..,An(σP(r1x r2 x..x rm))
■ select A1, A2, sum(A3)
 from r1, r2, …, rm
 where P

group by A1, A2
is equivalent to the following expression in multiset relational algebra A1, A2 sum(A3) (σP (r1 x r2 x .. x rm)))
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.67 ©Silberschatz, Korth and Sudarshan

Example Database
■ E-Commerce Database with customers, products, and purchases: CUSTOMER
CID
CNAME
CADDRESS
PURCHASE
CID
PID
TIMEDATE
PRICE
PRODUCT
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.68 ©Silberschatz, Korth and Sudarshan
PID
PNAME
PDESCRIPTION
PPRICE

Example Database
■ CIDs of Customers named “John Smith”
■ Names of customers who have ordered something costing >$10
■ Names customers who have ordered an item called “IPhone 9”
■ CID of customers named “John Smith” who have ordered an “IPhone9”
■ For each customer, how much money they have spent.
■ For each product, how many items were bought.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.69 ©Silberschatz, Korth and Sudarshan

Tuple Relational Calculus
■ A nonprocedural query language, where each query is of the form
{t | P (t ) }
■ It is the set of all tuples t such that predicate P is true for t
■ t is a tuple variable, t [A ] denotes the value of tuple t on attribute A
■ t ∈ r denotes that tuple t is in relation r
■ P is a formula similar to that of the predicate calculus
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.70 ©Silberschatz, Korth and Sudarshan

Predicate Calculus Formula
1. Set of attributes and constants
2. Set of comparison operators: (e.g., <, ≤, =, ≠, >, ≥) 3. Set of connectives: and (∧), or (v)‚ not (¬)
4. Implication (⇒): x ⇒ y, if x if true, then y is true
x ⇒ y ≡ ¬x v y
„ ∃ t ∈ r (Q (t )) ≡ ”there exists” a tuple in t in relation r

such that predicate Q (t ) is true
„ ∀t ∈ r (Q (t )) ≡ Q is true “for all” tuples t in relation r
5. Set of quantifiers:
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.71 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
{t | t ∈ instructor ∧ t [salary ] > 80000}
■ As in the previous query, but output only the ID attribute value
{t | ∃ s ∈ instructor (t [ID ] = s [ID ] ∧ s [salary ] > 80000)} Notice that a relation on schema (ID) is implicitly defined by
the query
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.72 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the names of all instructors whose department is in the Watson building
{t | ∃s ∈ instructor (t [name ] = s [name ] 

∧ ∃u ∈ department (u [dept_name ] = s[dept_name] “

∧ u [building] = “Watson” ))}
■ Find the set of all courses taught in the Fall 2009 semester, or in 

the Spring 2010 semester, or both
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

v ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.73 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the set of all courses taught in the Fall 2009 semester, and in 
 the Spring 2010 semester
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

∧ ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
■ Find the set of all courses taught in the Fall 2009 semester, but not in 
 the Spring 2010 semester
{t | ∃s ∈ section (t [course_id ] = s [course_id ] ∧ 

s [semester] = “Fall” ∧ s [year] = 2009) 

∧ ¬ ∃u ∈ section (t [course_id ] = u [course_id ] ∧ 

u [semester] = “Spring” ∧ u [year] = 2010)}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.74 ©Silberschatz, Korth and Sudarshan

Safety of Expressions
■ It is possible to write tuple calculus expressions that generate infinite relations.
■ For example, { t | ¬ t ∈ r } results in an infinite relation if the domain of any attribute of relation r is infinite
■ To guard against the problem, we restrict the set of allowable expressions to safe expressions.
■ Anexpression{t|P(t)}inthetuplerelationalcalculusissafeif every component of t appears in one of the relations, tuples, or constants that appear in P
● NOTE: this is more than just a syntax condition.
! E.g. { t | t [A] = 5 ∨ true } is not safe — it defines an infinite set with attribute values that do not appear in any relation or tuples or constants in P.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.75 ©Silberschatz, Korth and Sudarshan

Universal Quantification
■ Find all students who have taken all courses offered in the Biology department
● {t | ∃ r ∈ student (t [ID] = r [ID]) ∧

(∀ u ∈ course (u [dept_name]=“Biology” ⇒ 

∃s∈takes(t[ID]=s[ID]∧ 

s [course_id] = u [course_id]))}
● Note that without the existential quantification on student, the above query would be unsafe if the Biology department has not offered any courses.
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.76 ©Silberschatz, Korth and Sudarshan

Domain Relational Calculus
■ A nonprocedural query language equivalent in power to the tuple relational calculus
■ Each query is an expression of the form: {|P(x1,x2,…,xn)}

● x1, x2, …, xn represent domain variables
● P represents a formula similar to those in predicate
calculus
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.77 ©Silberschatz, Korth and Sudarshan

Example Queries
■ Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
● {| ∈instructor∧s>80000}
■ As in the previous query, but output only the ID attribute value
● { |∃n,d,s(∈instructor∧s>80000)} ■ Find the names of all instructors whose department is in the
Watson building
{| ∃i,d,s(∈instructor

∧∃b,a(∈department ∧ b=“Watson”))}
Database System Concepts – 6th Edition
Modified by T. Suel for CS6083, NYU Tandon, Spring 2020
2.78 ©Silberschatz, Korth and Sudarshan